package main

import "fmt"

//8ms 87%, 6.3MB 54%
func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return nil
	}
	res := []int{}
	top, bottom, left, right := 0, len(matrix)-1, 0, len(matrix[0])-1
	for top <= bottom && left <= right {
		for i, j := left, top; i <= right; i++ {
			res = append(res, matrix[j][i])
		}
		top++
		for i, j := right, top; j <= bottom; j++ {
			res = append(res, matrix[j][i])
		}
		right--
		if top > bottom || right < left {
			break
		}
		for i, j := right, bottom; i >= left; i-- {
			res = append(res, matrix[j][i])
		}
		bottom--
		for i, j := left, bottom; j >= top; j-- {
			res = append(res, matrix[j][i])
		}
		left++
	}
	return res
}

func main() {
	fmt.Println(spiralOrder([][]int{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}))
	fmt.Println(spiralOrder([][]int{{1, 2, 3}, {5, 6, 7}, {9, 10, 11}}))
}
